package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}15:48
 */
public class LeetCode108 {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums,0,nums.length - 1);
    }

    // 方法一：中序遍历，总是选择中间的位置左边的数字作为根节点 这样就可以把长度为偶数的情况都考虑进来
    // 时间复杂度：O(n)O(n)，其中 nn 是数组的长度。每个数字只访问一次。
    // 空间复杂度：O(\log n)O(logn)，其中 nn 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 O(\log n)O(logn)
    public TreeNode helper(int[] nums,int left,int right){
        // 递归条件
        if (left > right){
            return null;
        }
        // 总是选中间的节点作为根节点
        int mid = (left + right) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums,left,mid - 1);
        root.right = helper(nums,mid + 1,right);
        return root;
    }

    // 方法二：中序遍历，总是选择中间位置右边的数字作为根节点
    public TreeNode helper2(int[] nums,int left,int right){
        // 递归条件
        if (left > right){
            return null;
        }
        // 总是选中间的节点（长度一半的右边）作为根节点
        int mid = (left + right + 1) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper2(nums,left,mid - 1);
        root.right = helper2(nums,mid + 1,right);
        return root;
    }

    public TreeNode helper3(int[] nums,int left,int right){
        if (left > right){
            return null;
        }
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[(left + right) / 2]);
        root.left = helper3(nums,left,mid - 1);
        root.right = helper3(nums,mid + 1,right);
        return root;
    }

}
